This application is directed to parallel processing, parallel switching networks, and particularly to an improved adaptation of serial fiber or copper wire and wireless transmission media to parallel switching networks for the purpose of interconnecting large numbers of processors with a minimal interface. With the interconnection network it is possible to connect individual processing elements on chips, say of the kind of Li et al, U.S. Pat. No. 4,783,738, issued Nov. 8, 1988, through a network. Through this minimal interface nodes can interact in parallel and form gateways to other nodes and networks, via bridges which may be of wire, fiber optics, wireless radio or other through the air or space transmissions. Thus the switch may form the basis of a generic network of great size and flexibility. The processors can be heterogeneous or homologous and the computer systems which are created by the developments have wide application. Some of these will be described in detail.
The inventions relate to networks. Networks of some type have existed for many years to connect sending devices to receiving devices, and the early networks were telephone related. Coexisting with these networks have been radio and other wireless transmitters and receivers. In recent years there has been a connections of wireless devices to land based systems. However, the existing systems have been to expensive and not sufficiently flexible for high speed parallel coupling of nodes over a network. This has remained a problem despite numerous prior developements and theory.
The practitioner in the computer field will be trained in some networks today. However, as there are many types, the training will not extend to the many available possibilities which have been developed in the network art.
Among the most commonly used networks for digital communication between processors are the Ethernet or Token Ring of LAN networks. "Ethernet: Distributed Packet Switching for Local Computer Networks" Communications of the ACM, July 1976, Vol. 19, No. 7, pp. 395-404; and "Token-Ring Local-Area Networks and Their Performance, W. Bux, Proceedings of the IEEE, Vol 77, No. 2, February 1989, pp 238-256; are representative articles which describe this kind of network, which provide a serial shared medium used by one node at a time to send a message to another node or nodes.
"Data Networks", D. Bertsekas, R. Gallager, Prentice Hall, Inc. 1987, ISBN 0-13-196825-4 025, is a book which describes generally the art of data networks. It describes a broad range of networks and node-to-node communication, drawing on the works of others. FIG. 1.3 at Page 3 illustrates what is considered as a generic network, to which the inventions herein relate. It draws upon the work of many others but falls short in suggesting the solutions achieved by the present inventions.
There are many kinds of networks. "A Survey of Interconnection Networks", T. Feng, IEEE COMPUTER, 0018-1962/81/1200-0012, December 1981, pp 12-27, describes and categorizes the networks of the art. The present application describes something which would be classified as a dynamic network topology, which is of a non-blocking nature. Unlike the restricted networks described the network described in this application can be made to implement a variety of possible network designs. Other papers relating to high level considerations which may be reviewed include: "The Theory of Connecting Networks and Their Complexity: A Review", M. Marcus, Proceedings of the IEEE, Vol 65, No. 9, September 1977, pp 1263-1271; and "Interconnection Networks for SIMD Machines, H. Siegel, IEEE COMPUTER, June 1971, 018-9162/79/0600-0057, pp. 57-65.
Historically many kinds of networks were developed for the telephone system. Telephone switching is described in "Circuit Switching: Unique Architecture and Application", A. Joel, Jr., IEEE COMPUTER, June 1979, 018-9162/79/0600-0010, pp 10-22; however, this article considers circuit switching with time-multiplexing and frequency-multiplexing of messages simultaneously onto the same transmission medium, which ideas are not implemented in the preferred embodiment of the inventions here. There are nevertheless networks and network theory which has been developed for non-blocking telephone device to device interconnection. For instance, the CLOS network has been developed. Such kind of network could be formed by the presently described switch, but as will be appreciated from reading the detailed description of the inventions, the CLOS network does not suggest or describe our inventions. The basic work of Clos in non- blocking networks is thought to be "A Study of Non-Blocking Switching Networks", C. Clos, The Bell System Technical Journal, Vol. XXXII, March 1953, pages 406-424. It described a general method for making a network non-blocking (in a manner different from the present inventions preferred embodiment) by making the network large enough to always be able to connect an input to an output by adding more paths or stages to the network. This solution increase greatly costs of a network.
Other networks which could be created by the present inventions include complete and incomplete Hypercubes and Benes networks which are in turn derived from Clos. Hypercube type networks are described in "Incomplete Hypercubes", H. Katseff; IEEE Transactions on Computers, Vol. 37, No. 5, May 1988, 0018-9340/88/0500-0604, pp. 604-608; "Generalized Hypercube and Hyperbus Structures for a Computer Network", L. Bhuyan et al, IEEE Transactions on Computers, Vol. C-33, No. 1, April 1984, pp. 323-333 (EH0246-9/86/0000/0307-1984 IEEE); and The Indirect Binary n-Cube Microprocessor Array, M. Pease, III; IEEE Transactions on Computers, Vol C.26, No. 5, May 1977; pp 458-473. While a hypercube structure could be implemented with the present inventions, it is not our preferred embodiment. The hypercube can be much slower due to relays though nodes than is possible with the present structure of the preferred embodiment. Similarly, the Benes network, as described in "Parallel Permutations of Data: A Benes Network Control Algorithm for Frequently Used Permutations", J. Lenfant, IEEE Transactions on Computers, VOl. C-27, No. 7, July 1978, pp 637-647, uses switches in a recurrent structure with a software algorithm for selecting a route. While such a structure could be implements with the switch of the present inventions, in our preferred embodiment the hardware is used to find a path through a parallel network, again something not suggested here.
Shuffle networks are still another kind of network. Parallel processing with a network as described in "Parallel Processing with the Perfect Shuffle", H. Stone, IEEE Transactions on Computers, Vol C-20, No. 2, Feb. 1971 is a particular kind of multi-stage network with an interconnection pattern which is described as "Perfect Shuffle". This kind of network has better scalabability characteristics than some other networks, and sometimes can achieve good performance. Another application of a shuffle network is for SIMD, as described in "On the Augmented Data Manipulator in SIMD Environments", K. Lee et al, IEEE Transactions on Computers, Vol 37, No. 5, May 1988; pp 574-584; and in one of the related applications referenced above such a machine is disclosed. This perfect shuffle also could be implemented by the present structure, but the system which we have described for search has better non-blocking characteristics. It is also faster than any other known network, with extremely low message latency.
There are many, many facets for integrating computer systems, and with the move to open systems and distributed processing, those working at the highest level of expertise in the art continue to plow the ground of those who developed the theories elucidated in the past. The articles published in Proceedings, COMPUTER NETWORKING SYMPOSIUM, IEEE Computer Society, April 11-13, 1988, lEE Catalog 88-CH2547-8, recognize the problems associated with heterogeneous environments and describe many protocols under consideration; while the Working Implementation Agreements for Open Systems Interconnection Protocols, F. Boland, Vol. 2, No. 1, 1989 Reprint Edition of NISTIR 89-4198, IEEE Computer Society Press, No 2042, ISBN 0-8186-2042-0, worked on message format and other aspects of file transfer between disparate systems which are generally used in commerce today. However, as indicated by the various articles in the Proceedings Vol. III, Ninth Annual Joint Conference on IEEE Computer and Communication Societies, The Multiple Facets of Integration; June 1990, IEEE Society Press. Cat No. 90CH2826-5 using the systems of the past requires much adaptation and considerable work, and there are many limitations which still need to be overcome particularly when many processors are intercoupled to send data between themselves.
The above articles may be supplemented by the patent literature. For instance, several patents may be contrasted to the present inventions. U.S. Pat. No. 4,484,325--4-WAY SELECTOR SWITCH, and U.S. Pat. No. 4,475,188--4-WAY ARBITRATION SWITCH, describe a switch itself, rather than a switch having any adapter for converting serial data to parallel switch data. The switch itself does not provide interfaces to fiber optics or standard protocols, which is an object of the present invention. The switch is not programmable or adaptable to various protocols--if fact it implements its own unique (non-standard) protocol. This switch is organized as a 5 port solution which may allow better latency to the nearest neighbors, but increasingly worse latency to for larger systems. The switch is not equi-distant from all nodes, as is the present invention, which causes communication latency imbalance and difficulty of software routing and software switch management. The switch transfers one bit at a time with each bit requiring an individual handshake, which provides an unbelievably slow communication method--especially through a network. In contrast the present switch handshakes only the transmission of the entire message, which can be thousands or millions of bits--and thus provides a thousand or million times speed improvement. U.S. Pat. No. 4,482,996--Five Pod Node, appears to be associated with the above patents and this patent relates to a node that attaches to the switch, rather than an adapter or a switch.
U.S. Pat. No. 4,307,446--Digital Networks Employing Speed Independent Switches deals with smaller selector and arbitration switches. It describes any combination of one or two input and output ports, but not larger. This patent has the problems mentioned, except this doesn't require a LAN connection and permits multi-stage networks. However, the small size switch may be okay for small systems, but cumbersome and slow for massively parallel systems. It also provides a non-standard serial interface directly and is not provided with anything like the adapters here disclosed, nor does it appear to have considered any flexibility to handle various protocols.
Other patents which may be thought by some to have some elements which are in common with those of the disclosure include: U.S. Pat. No. 4,929,939, entitled High Speed Switching System with Flexible Protocol Capability, by C. J. Georgious and T. A. Larsen. It generally describes a modular multi-plane cross-point switching system which allows efficient switching of both short and long messages. The switching system consists of two distinct types of switching planes, data planes and control/data planes. The data planes are used solely for the purpose of transferring data and contain no hardware to extract control information from the message or to determine the setting of the crosspoints in the plane. The control/data planes perform the dual functions of transferring data as well as setting up the switch planes based on control information extracted from the message. The system provides two modes for communication between processors. Shod messages are switched through the control/data planes using message switching to achieve low latency. Long messages are transferred by distributing the data across all the switching planes by means of a protocol based on circuit switching. The basic switch is for a plurality of processors, and the switching station comprises a plurality of switching planes for transferring data therethrough; a plurality of data links, each of said data links being coupled at a first end thereof to a respective one of said switching planes and at a second end thereof to one of said processors; at least one of said switching planes is a control/data plane with controls for controlling the transfer therethrough of data and for controlling data transfer through other of said switching planes; and the switching station is operable in a first mode wherein only said one switching plane is used for data transfer and in a second mode wherein said one switching plane and said other switching planes are used for data transfer. This type of switching system may be called a collision crossbar. It requires at least 10 clocks to set up every stage, is synchronous, and requires up to 5 different networks working in harmony to function properly. Basically it is slower, more expensive than the present ALLNODE Switch--and requires complex synchronization. It is an attempt to make one large crossbar to interconnect all nodes rather than using a multi-stage network. They attempt to solve the-large crossbar pin problem by making the crossbar only 1 bit wide and calling it a switch plane, and using several or many switch p lanes in parallel to get wider data transfers. It uses data planes and control planes and combinations of the two. However, the various planes must be synchronized and problems exist in resolving contention for a given node that could lead to circuit stressing and degraded performance. The various multiple planes are not needed with the present improvements. Another patent of the same nature is represented by the CROSS-POINT SWITCH OF MULTIPLE AUTONOMOUS PLANES, U.S. Pat. No. 4,695,999, which also shows a multi-plane cross-point switching system in which a communication message from a sender is shown. Here the communication is divided into a plurality of data links which are separately connected through autonomous cross-point switches to the receiver where the links are recombined. The cross-points in each plane are separately set by control messages transmitted along with the separate parts of the divided message. While divided messages are possible with the present invention the means disclosed is complex and not simple. Synchronizing planes is still a problem here. The ALLNODE Switch avoids these problems and operates more simply. Further this prior patent cannot adapt various serial protocols to communicate to each other as the present disclosure does; they cannot intermix serial and parallel transfers.
U.S. Pat. No. 4,763,122 entitled Parallel Switching with Round Robin Priority, by P. A. Franaszek, describes another scheme for determining priority of users for a transmission line. This also occurs in the cross point switch described described in U.S. Pat. No. 4,929,939, where multiple planes are used. U.S. Pat. No. 4,763,122 describes how some of these planes can be used to perform a round robin priority scheme which is not needed with the disclosed apparatus.
U.S. Pat. No. 4,961,140 entitled A NEW ADDRESS/DATA/COMMUNICATION INPUT OUTPUT BUS INCLUDING A NEW COMMANDS AND INSTRUCTIONS BEING USED AS A RESULT OF THE NEW IMPLEMENTATION OF THE NEW BUS IN A MULTIPROCESSOR COMPUTER SYSTEM describes a single processor to multiple I/O device interface over a bus rather than a switch. This describes something like a microchannel bus and is related only in that the present preferred embodiments can communicate via a microchannel bus.
U.S. Pat. No. 4,803,485--LAN COMMUNICATION SYSTEM, represents a LAN approach which use of the present inventions would replace. This patent describes a medium conversion adapter similar to the present invention, but for adapting various protocols to a communication system having multiple transmission medium segments in a ring configuration, like a token ring or LAN. The token ring can have fiber or metallic interconnections. The present invention differs in that it adapts multiple transmission medium segments in an unbuffered multi-stage parallel transfer configuration, that gets latencies in the sub-microsecond range, rather than in the millisecond range of LAN's, that provides simultaneous and equi-distant communication paths, whose transmission bandwidth and number of simultaneous paths scale with increased system size. The present invention is the replacement for the state-of-the-art LAN approach that reduce latency and improve bandwidth by many orders of magnitude. These differences will be of value in the future.
Harold Stone in his book "High-Performance Computer Architecture", Addison Wesley 1990 recognizes (p. 309) that there is a need in architectures which are parallel for machine mechanisms which minimize overhead required among processors jointly working on the job. The overhead needed need to be solved, and effectively. Interconnection thorough existing networks is slow, and with heterogeneous networks for large interactive data exchanges intolerably slow. While more detail will be found in the detailed description below, it should be recognized that there is a need for an inexpensive high speed switching device which can be used as a "generic". This is an achievement of the present inventions. The achievement allows creating of many new computer systems with heterogeneous and homologous processors, and can be used as a generic network interconnection device for high speed transfers.